/*线段树 单点修改 
区间修改需要懒标记
* 1.原理
    满二叉树，用一维数组存整棵树

    当前编号是x, 父节点 x >> 1
                左孩子 2x
                右孩子 2x+1

    除最后一层外我们有2n−1个节点
    最后一层最多有2n个节点
    总的节点数不会超过4n−1个节点

* 2.操作
    push_up：由子节点计算父节点
    build：将一段区间初始化成线段树
    modify：修改操作 —— 修改单点或修改区间
    query：查询操作，即查询某一段线段树的信息
    push_down（懒标记、延迟标记）：由父节点计算子节点

* 3.build 构造
    //u：当前节点编号
    //l：当前区间的左端点
    //r：当前区间的右端点
    void build(int u, int L, int R)
    {      
        tree[u].l = L, tree[u].r = R; //将左右端点存入
        if(c == k) return; //如果当前节点为叶子节点，退出
        int mid = L + R >> 1; //计算当前区间中点
        build(u<<1, L, mid);
        build(u<<1|1, mid + 1, R);   
        //push_up(u);//一般会在此时进行push_up操作
        
    }

* 4.递归范围
    查询范围[L, R]
    (1)当前节点[Tl, Tr]整体被包含[L, R] <-> [Tl,Tr]⊂[L,R] <-> L <Tl < Tr < R 
    直接返回当前节点权值

    (2)存在交集, 但不全包含, 则向下递归

    (3)不存在交集, 不存在这种情况

* 本题:
    完备性
    子节点向父节点转移, 存在父节点最大连续子段和是跨越左右端点的情况, 不能保证直接由vmax转移得到
    vmax = 三种情况：
    1.左子节点的最大连续子段和 l.vmax;
    2.右子节点的最大连续子段和 r.vmax;
    3.左子节点的最大后缀和 {l.rmax} + 右子节点的最大前缀和 {r.lmax}。

    -> u.vmax=max(l.rmax+r.lmax, max(l.vmax, r.vmax));
       u.lmax=max(l.lmax, l.sum+r.lmax);
       u.rmax=max(r.rmax, r.sum+l.rmax);
       u.sum=l.sum+r.sum;
*/
// #define ONLINE_DUDGE
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e6+10;
#define L(u) (u << 1) // 左孩子
#define R(u) (u << 1 | 1) // 右孩子

struct Node
{
    int l, r;
    int vmax, lmax, rmax; // 最大连续字字段和 最大前缀和 最大后缀和 
    int sum; // 区间和
}tree[N << 2];

int n, m, A[N];

void push_up(Node &U,Node &L, Node &R) // 函数重载
{
    U.vmax=max(L.rmax+R.lmax, max(L.vmax, R.vmax));
    U.lmax=max(L.lmax, L.sum+R.lmax);
    U.rmax=max(R.rmax, R.sum+L.rmax);
    U.sum=L.sum+R.sum;
}

void push_up(int u) // u的孩子节点更新u的权值
{
    push_up(tree[u], tree[L(u)], tree[R(u)]);
    
}

void build(int u, int l, int r)
{      
    
    if(l == r) {tree[u] = {l, r, A[l], A[l], A[l], A[l]}; return;}//如果当前节点为叶子节点，退出
    
    tree[u].l = l, tree[u].r = r; //将左右端点存入
    int mid = l + r >> 1; //计算当前区间中点
    build(L(u), l, mid);
    build(R(u), mid + 1, r);   
    push_up(u);//一般会在此时进行push_up操作
}

Node query(int u, int l, int r) // 需要区间合并时,需要左右节点的所有信息, 返回Node方便更新
{
    auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
    if(l <= U.l && U.r <= r) return U; // 被完全包含

    int mid = (U.l + U.r) >> 1;
    if(r <= mid) return query(L(u), l, r); // 范围整体在左区间
    else if(l > mid) return query(R(u), l, r); // 范围整体在右区间
    else{ // 与左区间和右区间同时有交集
        auto left = query(L(u), l, r);
        auto right = query(R(u), l, r);
        Node res;
        push_up(res, left, right); // 计算虚拟节点的权值
        return res;
    }

}

void modify(int u, int x, int v) // 当前节点 待修改节点的位置 修改目标值
{
    auto &U = tree[u], &L = tree[L(u)], &R = tree[R(u)];
    if(U.l == x && U.r == x) {U = {x, x, v, v, v, v}; return;}// 找到叶子节点x
    
    int mid = U.l + U.r >> 1;
    if(x <= mid) modify(L(u), x, v);
    else modify(R(u), x, v);
    push_up(u);
}

signed main()
{
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);   
	cin.tie(0);
    #else
    freopen("./in.txt","r",stdin);
    #endif

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> A[i];

    build(1, 1, n);

    int k, x, y;
    while(m--)
    {
        cin >> k >> x >> y;
        if(k == 1){ // 询问
            if(x > y) swap(x, y);
            cout << query(1, x, y).vmax << endl;
        }
        else{
            modify(1, x, y); // A[x]+y
        }
    }
    return 0;
}
